package com.julius.design.suanfa.sort;

import java.util.*;

/**
 * @author julius
 * @date 2021-11-12 上午 10:28
 * <p>
 *      查找数组的中位数
 *
 *      如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 *
 *      例如，
 *
 *      [2,3,4] 的中位数是 3
 *
 *      [2,3] 的中位数是 (2 + 3) / 2 = 2.5
 *
 *      设计一个支持以下两种操作的数据结构：
 *
 *      void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 *      double findMedian() - 返回目前所有元素的中位数。
 *
 *      链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
 * </p>
 */
public class MedinaFinder {


    /**
     * 重点是如何设计数据结构。设计一个有序list
     */
    private List<Integer> sortList;

    /** initialize your data structure here. */
    public MedinaFinder() {
        sortList = new ArrayList<>();
    }

    public void addNum(int num) {
        //在添加的时候直接排序,转化为一个在序数组中插入一个值，保证数组的有序性
        addSortList(num);
    }

    /**
     *  有序的添加到一个有序数组中
     *  时间复杂度较高（因为在插入后要将后续元素全部移动）
     *  使用链表，查询的时候较慢
     *  可以使用堆（大小顶堆）来减少添加元素时间复杂度，查找中位数只需要用到栈顶元素
     *  */
    public void addSortList(int num){
        //这样是无序的，要保证升序
        int size = sortList.size();
        if(size == 0){
            sortList.add(num);
            return;
        }

        //找到比当前元素大的第一个位置
        for (int i = 0; i < size ; i++) {
            if(sortList.get(i) > num){
                sortList.add(i,num);
                return;
            }
        }
        sortList.add(num);

    }

    public double findMedian() {
        int size = sortList.size();
        if(size == 0){
            return 0;
        }
        //根据size的奇偶性判断中位数
        Integer integer = sortList.get(size / 2);
        if(size % 2 == 0 ){
            Integer integer1 = sortList.get(size / 2 - 1);
            return (integer+integer1)/2.0;
        }else{
            return integer;
        }
    }


    /* **************************************** 大小顶堆排序 ******************************************** */
    Queue<Integer> A ,B;

    public MedinaFinder(int a){
        //小顶堆，保存较大的一半
        A = new PriorityQueue<>();
        //大顶堆。保存较小的一半
        B = new PriorityQueue<>((x,y)->(y-x));
    }

    public void addNum2(int num){
        if(A.size() != B.size()){
            //大小顶堆不一样大小
            A.add(num);
            B.add(A.poll());
        }else{
            B.add(num);
            A.add(B.poll());
        }
    }

    public double find2(){
        if(A.size() == B.size()){
            return (A.peek()+B.peek())/2.0;
        }else{
            return A.peek();
        }
    }
    public static void main(String[] args) {
        MedinaFinder obj = new MedinaFinder();
        while (obj.sortList.size() <= 20){
            Random random = new Random();
            obj.addNum(random.nextInt(100));
        }

        for (int i = 0; i < obj.sortList.size() ; i++) {
            System.out.print(obj.sortList.get(i)+" ");
        }
        System.out.println();
    }
}
